Xem chi tiết: Mật mã hóa khóa công khai

Các thuật toán Mã hóa khóa đối xứng có một số trở ngại không thuận tiện — hai người muốn trao đổi các thông tin bí mật cần phải chia sẻ khóa bí mật. Khóa cần phải được trao đổi theo một cách thức an toàn, mà không phải bằng các phương thức thông thường vẫn dùng để liên lạc. Điều này thông thường là bất tiện, và mật mã hóa khóa công khai (hay khóa bất đối xứng) được đưa ra như là một giải pháp thay thế. Trong mật mã hóa khóa công khai có hai khóa được sử dụng, là khóa công khai (hay khóa công cộng) và khóa bí mật (hay khóa cá nhân), trong đó khóa công khai dùng để mật mã hóa còn khóa bí mật dùng để giải mật mã (cũng có thể thực hiện ngược lại). Rất khó để có thể thu được khóa bí mật từ khóa công khai. Điều này có nghĩa là một người nào đó có thể tự do gửi khóa công khai của họ ra bên ngoài theo các kênh không an toàn mà vẫn chắc chắn rằng chỉ có họ có thể giải mật mã các thông điệp được mật mã hóa bằng khóa đó.

Các thuật toán khóa công khai thông thường dựa trên các vấn đề toán học với độ khó NP. Ví dụ RSA, dựa trên độ khó (ước đoán) của bài toán phân tích ra thừa số nguyên tố. Vì lý do thuận tiện, các hệ thống mật mã hóa lai ghép được sử dụng trong thực tế; khóa được trao đổi thông qua mật mã khóa công khai, và phần còn lại của thông tin được mật mã hóa bằng cách sử dụng thuật toán khóa đối xứng (điều này về cơ bản là nhanh hơn). Mật mã hóa đường cong elip là một dạng thuật toán khóa công khai có thể có một số ưu điểm so các hệ thống khác.

Mật mã hóa bất đối xứng cũng cung cấp cơ chế cho chữ ký số, là cách thức để xác minh với độ bảo mật cao (giả thiết cho rằng khóa cá nhân liên quan được đảm bảo giữ an toàn) rằng thông điệp mà người nhận đã nhận được là chính xác được gửi đi từ phía người gửi mà họ yêu cầu. Các chữ ký như vậy thông thường (theo luật định hay được suy diễn mặc định) được coi là chữ ký số tương đương với chữ ký thật trên các tài liệu được in ra giấy. Xét về phương diện kỹ thuật, chúng lại không phải vậy do không có sự tiếp xúc thực tế mà cũng không có liên hệ giữa "người ký" và "chữ ký". Sử dụng hợp thức các thiết kế có chất lượng cao và các bổ sung khác tạo ra khả năng có được độ an toàn cao, làm cho chữ ký điện tử vượt qua phần lớn các chữ ký thật cẩn thận nhất về mức độ thực của nó (khó bị giả mạo hơn). Các ví dụ về các giao thức chữ ký số hóa bao gồm DSA và chữ ký ElGamal. Các chữ ký số hóa là trung tâm trong các hoạt động của hạ tầng khóa công cộng (PKI) và rất nhiều hệ thống an ninh mạng (ví dụ Kerberos, phần lớn các mạng riêng ảo (VPN) v.v). Giống như mật mã hóa, các thuật toán lai ghép thông thường được sử dụng trong thực tế, thay vì ký trên toàn bộ chứng từ thì hàm băm mật mã hóa của chứng từ được ký.

Mật mã khóa bất đối xứng cũng cung cấp nền tảng cho các kỹ thuật khóa thỏa thuận xác thực mật khẩu (PAKA) và không kỹ năng kiểm chứng mật khẩu (ZKPP). Điều này là quan trọng khi xét theo phương diện của các chứng minh lý thuyết và kinh nghiệm rằng việc xác thực chỉ bằng mật khẩu sẽ không đảm bảo an toàn trên mạng chỉ với khóa mật mã đối xứng và các hàm băm.